ProgrammingAlgorithm

백준 13459 째로탈출

Algorithm

백준 째로 탈출은 10번이라는 횟수의 제한 안에 파란 구슬을 빼지 않으면서 빨간 구슬을 뺄 수 있는지 시뮬레이션을 해보는 문제이다.

bfs를 통해서 현재 빨간 구슬, 파란구슬의 위치에 대해 상,하, 좌,우 움직인 좌표가 어디인지를 확인해 나가면 풀 수 있는 문제이다. 생각보다 구현도 짜증나고 상,하,좌,우 움직였을 때 일단 한쪽으로 구슬을 몰아 넣은 다음에 다시 구슬의 위치를 판단해 주어야 하기 때문에 이 부분이 핵심이고 이 부분만 잘 구현한다면 풀 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#pragma warning(disable:4996)
#include<iostream>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<stdlib.h>
#include<string>
#define INF 999999999999
#define ll long long
using namespace std;

int n, m;

char map[11][11];

int visited[11][11][11][11];

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

struct Pos
{
	int rx, ry, bx, by;

	Pos() {}
	Pos(int redx, int redy, int bluex, int bluey)
	{
		rx = redx;
		ry = redy;
		bx = bluex;
		by = bluey;
	}
};


int main()
{
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;

	int redx, redy, bluex, bluey;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 'R')
				redx = i, redy = j;
			if (map[i][j] == 'B')
				bluex = i, bluey = j;
		}
	}

	queue<Pos> queue;
	visited[redx][redy][bluex][bluey] = 1;
	queue.push(Pos(redx, redy, bluex, bluey));


	int cnt = 0;

	while (!queue.empty())
	{
		int qsize = queue.size();

		for (int i = 0; i < qsize; i++)
		{
			int crx = queue.front().rx;
			int cry = queue.front().ry;
			int cbx = queue.front().bx;
			int cby = queue.front().by;
			queue.pop();

			if (map[crx][cry] == 'O')
			{
				cout << 1 << endl;
				return 0;
			}

			for (int j = 0; j < 4; j++)
			{
				int nrx = crx, nry = cry, nbx = cbx, nby = cby;
				bool be = false;
				while (map[nrx+dx[j]][nry+dy[j]] != '#' && map[nrx][nry] != 'O')
				{
					nrx += dx[j];
					nry += dy[j];
				}

				while (map[nbx+dx[j]][nby+dy[j]] != '#'&&map[nbx][nby] != 'O')
				{
					nbx += dx[j];
					nby += dy[j];

					if (map[nbx][nby] == 'O')
						be = true;
				}

				if (nrx == nbx&&nry == nby)
				{
					if (j == 0)
					{
						if (cry > cby)
							nby -= 1;
						else
							nry -= 1;

					}
					else if (j == 1)
					{
						if (cry > cby)
							nry += 1;
						else
							nby += 1;
					}
					else if (j == 2)
					{
						if (crx > cbx)
							nbx -= 1;
						else
							nrx -= 1;
					}
					else
					{
						if (crx > cbx)
							nrx += 1;
						else
							nbx += 1;
					}
				}


				if(be)continue;

				if (visited[nrx][nry][nbx][nby])
					continue;
				queue.push(Pos(nrx, nry, nbx, nby));
				visited[nrx][nry][nbx][nby] = 1;

			}
		}


		cnt++;
		if (cnt > 10) break;
	}

	cout << 0 << endl;
	return 1;
}
공유하기